package com.sendi.system.util.common;

import java.text.DecimalFormat;
/**
* 经分析知：希尔排序和堆排序性能最好
*  
*/
public class Sorting {
	private static long COMPARE = 0; //关键字比较次数
	private static long MOVE = 0; //关键字移动次数

		/**
	    * 起泡排序
	    * 时间复杂度最好为n-1，最差为n*(n-1)/2
	    * 空间复杂度为1
	    * 稳定排序
	    */
	public void bubbleSort(byte[] src) {
	    for (int i = 0; i < src.length; i++) {
	     boolean flag = true;
	     for (int j = 0; j < src.length - 1 - i; j++) {
	      if (src[j] > src[j + 1]) {//最大的数沉底
	       byte temp = src[j];
	       src[j] = src[j + 1];
	       src[j + 1] = temp;
	       flag = false;
	       MOVE += 3;
	      }
	      COMPARE++;
	     }
	     if (flag) {
	      break;
	     }
	    }
	}

	/**
	    * 选择排序
	    * 时间复杂度为1+2+3+..+n-1=n*(n-1)/2
	    * 空间复杂度为1
	    * 稳定排序
	    */
	public void selectSort(byte[] src) {
	    for (int i = 0; i < src.length - 1; i++) {
	     //每次循环的第一个位置存入最大值
	     for (int j = i + 1; j < src.length; j++) {
	      if (src[i] > src[j]) {
	       byte temp = src[i];
	       src[i] = src[j];
	       src[j] = temp;
	       MOVE += 3;
	      }
	      COMPARE++;
	     }
	    }
	}

	/**
	    * 直接插入排序
	    * 时间复杂度最好为n-1, 最差为1+2+3+..+n,平均为n*n/4
	    * 空间复杂度为1
	    * 稳定排序
	    */
	public void insertSort(byte[] src) {
	    for (int i = 0; i < src.length - 1; i++) {
	     int j = i + 1;//指向有序序列之后的位置
	     byte temp = src[j];//取有序序列之后的一个数
	     MOVE++;
	     //(从有序序列最后一个数)开始向前和(有序序列之后的一个数)比较并后移
	     for (; j - 1 >= 0/*防止下溢出*/&& src[j - 1] > temp; j--) {
	      src[j] = src[j - 1];//后移
	      COMPARE++;
	      MOVE++;
	     }
	     src[j] = temp;//插入之前进行了j--运算
	     MOVE++;
	    }
	}

	/**
	    * 直接插入排序(折半查找)
	    * 时间复杂度最好为n-1, 最差为1+2+3+..+n,平均为n*n/4
	    * 空间复杂度为1
	    * 稳定排序
	    */
	public void insertSort2(byte[] src) {
	    for (int i = 0; i < src.length - 1; i++) {
	     byte temp = src[i + 1];//预取后一个数
	     MOVE++;
	     int low = 0;
	     int high = i + 1;
	     //在src[low...high]之间折半查找
	     while (low <= high) {
	      int mid = (low + high) / 2;//取值偏低1格，可能取到0
	      if (temp < src[mid]) {
	       high = mid - 1;//由于mid取值偏低1格,mid-1造成最终指向插入位之前2格
	      } else {
	       low = mid + 1;//由于mid取值偏低1格,mid+1进行了修正，low最终指向插入位
	      }
	      COMPARE++;
	     }
	     int j = i + 1;
	     /*此处只能用low作为条件且不可取等号，因为:
	      mid取值偏低1格,mid+1进行了修正，low最终指向插入位
	      而low最小值取到0，下限不可能越界*/
	     while (j > low) {
	      src[j] = src[j--];//后移
	      MOVE++;
	     }
	     src[j] = temp;//插入之前进行了j--运算
	     MOVE++;
	    }
	}

	/**
	    * 希尔排序(缩小增量排序)
	    * 时间复杂度最好为n
	    * 不稳定排序
	    */
	public void shellSort(byte[] src) {
	    int t = (int) (Math.log(src.length - 1) / Math.log(2));//增量序列的长度
	    for (int k = 1; k <= t; k++) {
	     int Δ = (int) Math.pow(2, t - k + 1) - 1;//产生增量序列...127, 63,31,15,7,3,1
	     for (int i = 0; i < src.length - Δ; i++) {
	      byte temp = src[i + Δ];
	      MOVE++;
	      int inLoc = i + Δ;//inLoc用于指向插入位置
	      while (inLoc - Δ >= 0/*防止下溢出*/&& src[inLoc - Δ] > temp) {
	       src[inLoc] = src[inLoc -= Δ];//后移
	       COMPARE++;
	       MOVE++;
	      }
	      src[inLoc] = temp;//插入之前进行了inLoc-=Δ运算
	      MOVE++;
	     }
	    }
	}

	/**
	    * 快速排序(分治法,定位枢轴法),不适合大文件排序，会造成堆栈溢出
	    * 时间复杂度最好为n，在基本有序的情况下退化为1+2+3+...+length-1
	    * 空间复杂度为log(n)/log2
	    * 不稳定排序
	    * 第归算法
	    */
	public void quickSort(byte[] src) {
	    quickSelf(0, src.length - 1, src);
	}

	private void quickSelf(int low, int high, byte[] src) {
	    int pivot = partition(low, high, src);
	    if (low < pivot - 1) {//当原始低端位置小于枢轴位置
	     quickSelf(low, pivot - 1, src);//第归  
	    }
	    if (high > pivot + 1) {//当原始高端位置大于枢轴位置
	     quickSelf(pivot + 1, high, src);//第归
	    }
	}

	private int partition(int low, int high, byte[] src) {
	    byte pivotValue = src[low];//枢轴
	    MOVE++;
	    while (low < high) {
	     while (low < high && src[high] >= pivotValue) {
	      high--;//最终指向比枢轴小的位置
	      COMPARE++;
	     }
	     src[low] = src[high];//比枢轴小的移到低端
	     MOVE++;
	     while (low < high && src[low] <= pivotValue) {
	      low++;//最终指向比枢轴大的位置
	      COMPARE++;
	     }
	     src[high] = src[low];//比枢轴大的移到高端
	     MOVE++;
	    }//low=high
	    src[low] = pivotValue; //确定枢轴位置
	    MOVE++;
	    return low;//low=high
	}

	/**
	    * 堆排序(树型选择排序)
	    * 时间复杂度 < 2*n*log2(n)
	    * 空间复杂度为1
	    * 不稳定排序
	    */
	private void createHeap(int a, int b, byte[] src) {//子树调整为大顶堆
	    byte temp = src[a];//暂存堆顶
	    int inLoc = a;//大孩子上移位置
	    for (int i = a * 2; i < b; i *= 2) {
	     if (i + 2 <= b/*防止局部上溢出*/&& i + 2 < src.length/*防止上溢出*/&& src[i + 1] < src[i + 2]) {//指向较大的孩子
	      i += 2;//右孩子
	     } else {//最后一棵子树必定有左孩子
	      i += 1;//左孩子
	     }
	     COMPARE++;
	     if (temp < src[i]) {
	      src[inLoc] = src[i];//移至父级
	      inLoc = i;//loc记录temp的最终插入位置
	      MOVE++;
	     } else {
	      break;//根节点已经是最大(当a=0,b=1时死循环)
	     }
	     COMPARE++;
	    }
	    src[inLoc] = temp;
	    MOVE++;
	}

	public void heapSort(byte[] src) {
	    for (int i = src.length / 2 - 1; i >= 0; i--) {//从下到上建立大顶堆
	     createHeap(i, src.length - 1, src);
	    }
	    for (int i = src.length - 1; i > 0; i--) {
	     byte temp = src[0];//堆顶与堆尾互换
	     src[0] = src[i];
	     src[i] = temp;
	     MOVE += 3;
	     //从上到下重新调整为大顶堆
	     createHeap(0, i - 1, src);
	    }
	}

	/**
	    * 归并排序
	    * 时间复杂度n*log2(n)
	    * 空间复杂度为1
	    * 稳定排序
	    * 非第归算法
	    */
	public void mergeSort(byte[] src) {
	    int pass = (int) (Math.log(src.length) / Math.log(2)) + 1;//归并次数
	    for (int k = 0, index = 0; k < pass; k++, index = 0) {//合并pass趟
	     byte[] temp = new byte[src.length];
	     MOVE++;
	     int δ = (int) Math.pow(2, k);//每组元素个数
	     int Δ = (int) Math.pow(2, k + 1);//组起始位置间距
	     for (int a = 0, b = δ; a < src.length && b < src.length; a += Δ, b += Δ) {//分组
	      //开始按组合并，分成a,b两组
	      int i = a, j = b, aScope = a + δ, bScope = b + δ;//(aScope|bScope)有越界可能
	      //确保i|j在scope范围之内同时防止i++|j++越上界
	      while ((i < aScope && j < bScope) && (i < src.length && j < src.length)) {//组内合并
	       if (src[i] < src[j]) {//存入较小的元素
	        temp[index++] = src[i++];
	       } else {
	        temp[index++] = src[j++];
	       }
	       COMPARE++;
	       MOVE++;
	      }
	      while (i < aScope && i < src.length) {//复制组内剩余 
	       temp[index++] = src[i++];
	       MOVE++;
	      }
	      while (j < bScope && j < src.length) {
	       temp[index++] = src[j++];
	       MOVE++;
	      }
	     }
	     for (int i = 0; i < index; i++) {//将已归并的元素复制回去, 未归并的仍在源数组中
	      src[i] = temp[i];
	      MOVE++;
	     }
	    }
	}

	/**
	    * 基数排序
	    */
	public void baseSort(byte[] src) {

	}

	/**
	    * 对800k的文本文件排序的性能分析 
	    */
	public static void main(String[] arg) {
	    Sorting sort = new Sorting();
	    long start = System.currentTimeMillis();
	/*    byte[] src = new FileTools().getContent("./src/example/structure/b.txt");
	    //byte[] src = { 'f', 'a', 'n', 'g', 'c', 'b', 'i' };
	    //sort.bubbleSort(src);
	    //b.txt 比较:49,9938,9789 移动:74,0877,4638 耗时:00:01:15 750
	    //sort.selectSort(src);
	    //b.txt 比较:49,9995,0000 移动:     1348,1955 耗时:00:00:37 641
	    //sort.insertSort(src);
	    //b.txt 比较:24,6959,1546 移动:24,6979,1544 耗时:00:00:27 719
	    //sort.insertSort2(src);
	    //b.txt 比较:      152,4685 移动:24,6979,1544 耗时:00:00:16 766
	    //sort.quickSort(src);
	    sort.shellSort(src);
	    //b.txt 比较:      858,6201 移动:     3688,9091 耗时:00:00:00 422
	    //sort.heapSort(src);
	    //b.txt 比较:     2842,1214 移动:     1763,9281 耗时:00:00:00 406
	    //sort.mergeSort(src);
	    //b.txt 比较:     1480,9758 移动:     3188,7888 耗时:00:00:00 797
	    long end = System.currentTimeMillis();
	    sort.print(src);

	    System.out.println("\n比较:" + new DecimalFormat(",####").format(COMPARE));
	    System.out.println("移动:" + new DecimalFormat(",####").format(MOVE));
	    System.out.println("耗时:" + TimeTools.format(end - start));*/
	}

	private void print(byte[] src) {
	    for (int j = 1; j <= src.length; j++) {
	     System.out.print((char) src[j - 1]);
	     if (j % 150 == 0) {
	      System.out.println();
	     }
	    }
	}


}
